TDAArbolBinario

## Class ArbolBinarioClase<E>

- java.lang.Object
- - TDAArbolBinario.ArbolBinarioClase<E>

- Type Parameters:
    `E` - Tipo de dato de los rótulos de los nodos de árbol.
  All Implemented Interfaces:
    java.lang.Iterable<E>, BinaryTree<E>, GTTree<E>

      public class ArbolBinarioClase<E>
      extends java.lang.Object
      implements BinaryTree<E>

  Implementa parcialmente un BinaryTree mediante una ED que mantiene referencias al padre, hijo izquierdo y derecho de la posición.
  Author:
    FJoaquin (federico.joaquin@cs.uns.edu.ar)

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected BTPosition<E>` | `raiz`
    `protected int` | `tamańo`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `ArbolBinarioClase()` Inicializa un árbol binario vacío.
    `ArbolBinarioClase(E rot)` Inicializa un árbol binario de tamańo uno.
    `ArbolBinarioClase(java.util.Iterator<E> it, int altura)` Inicializa un árbol binario completo dada una altura y un iterador de elementos.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `TDALista.Position<E>` | `addLeft(TDALista.Position<E> v, E r)` Agrega un nodo con rótulo r como hijo izquierdo de un nodo dado.
    `TDALista.Position<E>` | `addRight(TDALista.Position<E> v, E r)` Agrega un nodo con rótulo r como hijo derecho de un nodo dado.
    `protected void` | `attach_goodrich_tamassia(TDALista.Position<E> p, BinaryTree<E> t1, BinaryTree<E> t2)` Corresponde a la implementación de operación Attach() según Goodrich & Tamassia.
    `void` | `attach(TDALista.Position<E> p, BinaryTree<E> t1, BinaryTree<E> t2)` Inserta a los árboles T1 y T2 como subárboles hijos de la hoja v (izquierdo y derecho respectivamente).
    `protected BTPosition<E>` | `checkPosition(TDALista.Position<E> p)` Valida que la ED interna de la posición se corresponda con la utilizada por la implementación actual.
    `java.lang.Iterable<TDALista.Position<E>>` | `children(TDALista.Position<E> v)` Devuelve una colección iterable de los hijos del nodo correspondiente a una posición dada.
    `protected void` | `clonar_arbol_completo(BTPosition<E> padre, java.util.Iterator<E> it, int altura)` Clona el subárbol binario completo a partir de la posición padre.
    `protected void` | `clonar(BTPosition<E> padre_local, TDALista.Position<E> padre_t, BinaryTree<E> t)` Método auxiliar utilizado por attach.
    `TDALista.Position<E>` | `createRoot(E r)` Crea un nodo con rótulo e como raíz del árbol.
    `boolean` | `hasLeft(TDALista.Position<E> v)` Testea si v tiene un hijo izquierdo.
    `boolean` | `hasRight(TDALista.Position<E> v)` Testea si v tiene un hijo derecho.
    `boolean` | `isEmpty()` Consulta si el árbol está vacío.
    `boolean` | `isExternal(TDALista.Position<E> v)` Consulta si una posición dada corresponde a un nodo externo.
    `boolean` | `isInternal(TDALista.Position<E> v)` Consulta si una posición corresponde a un nodo interno.
    `boolean` | `isRoot(TDALista.Position<E> v)` Consulta si una posición dada corresponde a la raíz del árbol.
    `java.util.Iterator<E>` | `iterator()` Devuelve un iterador de los elementos almacenados en el árbol en preorden.
    `TDALista.Position<E>` | `left(TDALista.Position<E> v)` Devuelve la posición del hijo izquierdo de v.
    `TDALista.Position<E>` | `parent(TDALista.Position<E> v)` Devuelve la posición del nodo padre del nodo correspondiente a una posición dada.
    `java.lang.Iterable<TDALista.Position<E>>` | `positions()` Devuelve una colección iterable de las posiciones de los nodos del árbol.
    `E` | `remove(TDALista.Position<E> v)` Elimina el nodo referenciado por una posición dada.
    `E` | `replace(TDALista.Position<E> v, E e)` Reemplaza el elemento almacenado en la posición dada por el elemento pasado por parámetro.
    `TDALista.Position<E>` | `right(TDALista.Position<E> v)` Devuelve la posición del hijo derecho de v.
    `TDALista.Position<E>` | `root()` Devuelve la posición de la raíz del árbol.
    `int` | `size()` Consulta la cantidad de nodos en el árbol.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

    - ### Methods inherited from interface java.lang.Iterable

      `forEach, spliterator`

- - ### Field Detail

    - #### raiz

          protected BTPosition<E> raiz

    - #### tamańo

          protected int tamańo

  - ### Constructor Detail

    - #### ArbolBinarioClase

          public ArbolBinarioClase()

      Inicializa un árbol binario vacío.

    - #### ArbolBinarioClase

          public ArbolBinarioClase(E rot)

      Inicializa un árbol binario de tamańo uno.
      Parameters:
        `rot` - Rótulo de la raíz del árbol creado.

    - #### ArbolBinarioClase

          public ArbolBinarioClase(java.util.Iterator<E> it,
                                   int altura)

      Inicializa un árbol binario completo dada una altura y un iterador de elementos. Para esto, clona la estructura y elementos de otro árbol binario completo que es recorrido mediante el iterador, siguiendo un recorrido en preorden.
      Parameters:
        `it` - Iterador del árbol binario completo a clonar, siguiendo un recorrido en pre-orden.
        `altura` - Altura correspondiente al árbol binario completo a clonar.

  - ### Method Detail

    - #### clonar_arbol_completo

          protected void clonar_arbol_completo(BTPosition<E> padre,
                                               java.util.Iterator<E> it,
                                               int altura)

      Clona el subárbol binario completo a partir de la posición padre. Para esto considera la altura de las raíces de los subárboles a clonar, y el recorrido en preorden que sigue el iterador de elementos del árbol binario clonado.
      Parameters:
        `padre` - Nodo al que se agregarán el subárbol izquierdo y derecho.
        `it` - Iterador del subárbol binario completo a clonar, siguiendo un recorrido en pre-orden.
        `altura` - Altura correspondiente del nodo padre en el árbol binario clonado.

    - #### attach_goodrich_tamassia

          protected void attach_goodrich_tamassia(TDALista.Position<E> p,
                                                  BinaryTree<E> t1,
                                                  BinaryTree<E> t2)
                                           throws TDALista.InvalidPositionException

      Corresponde a la implementación de operación Attach() según Goodrich & Tamassia. En el contexto de Estructuras de datos, esta implementación es considerada inválida.
      Throws:
        `TDALista.InvalidPositionException`

    - #### attach

          public void attach(TDALista.Position<E> p,
                             BinaryTree<E> t1,
                             BinaryTree<E> t2)
                      throws TDALista.InvalidPositionException

      Description copied from interface: `BinaryTree`
      Inserta a los árboles T1 y T2 como subárboles hijos de la hoja v (izquierdo y derecho respectivamente).
      Specified by:
        `attach` in interface `BinaryTree<E>`
        `t1` - árbol binario a insertar como hijo izquierdo de v.
        `t2` - árbol binario a insertar como hijo derecho de v.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida o el árbol está vacío, o v no corresponde a una hoja.

    - #### clonar

          protected void clonar(BTPosition<E> padre_local,
                                TDALista.Position<E> padre_t,
                                BinaryTree<E> t)

      Método auxiliar utilizado por attach. Clona los hijos de T a partir de la posición padre_t, y agrega a estas clonaciones como hijos de padre_local.
      Parameters:
        `padre_local` - Posición a la que se le agregan la clonación de los hijos izquierdo y derecho de padre_t en T.
        `padre_t` - Posición de T que seńala el padre de los hijos izquierdo y derecho a clonar.
        `t` - BinaryTree que contiene al nodo padre_t, y del que se clonarán los nodos hijos izquierdo y derecho de padre_t.

    - #### checkPosition

          protected BTPosition<E> checkPosition(TDALista.Position<E> p)
                                         throws TDALista.InvalidPositionException

      Valida que la ED interna de la posición se corresponda con la utilizada por la implementación actual.
      Parameters:
        `p` - Posición a validar.
      Returns:
        Referencia a BTPosiciin de la posicion validada, si esta es válida.
      Throws:
        `TDALista.InvalidPositionException` - Si la posición parametrizada no corresponde con la implementación actual, o referencia a null, o fue eliminada con anterioridad (rótulo null).

    - #### size

          public int size()

      Description copied from interface: `GTTree`
      Consulta la cantidad de nodos en el árbol.
      Specified by:
        `size` in interface `GTTree<E>`
      Returns:
        Cantidad de nodos en el árbol.

    - #### isEmpty

          public boolean isEmpty()

      Description copied from interface: `GTTree`
      Consulta si el árbol está vacío.
      Specified by:
        `isEmpty` in interface `GTTree<E>`
      Returns:
        Verdadero si el árbol está vacío, falso en caso contrario.

    - #### iterator

          public java.util.Iterator<E> iterator()

      Description copied from interface: `GTTree`
      Devuelve un iterador de los elementos almacenados en el árbol en preorden.
      Specified by:
        `iterator` in interface `java.lang.Iterable<E>`
      Specified by:
        `iterator` in interface `GTTree<E>`
      Returns:
        Iterador de los elementos almacenados en el árbol.

    - #### positions

          public java.lang.Iterable<TDALista.Position<E>> positions()

      Description copied from interface: `GTTree`
      Devuelve una colección iterable de las posiciones de los nodos del árbol.
      Specified by:
        `positions` in interface `GTTree<E>`
      Returns:
        Colección iterable de las posiciones de los nodos del árbol.

    - #### replace

          public E replace(TDALista.Position<E> v,
                           E e)
                    throws TDALista.InvalidPositionException

      Description copied from interface: `GTTree`
      Reemplaza el elemento almacenado en la posición dada por el elemento pasado por parámetro. Devuelve el elemento reemplazado.
      Specified by:
        `replace` in interface `GTTree<E>`
      Parameters:
        `v` - Posición de un nodo.
        `e` - Elemento a reemplazar en la posición pasada por parámetro.
      Returns:
        Elemento reemplazado.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.

    - #### root

          public TDALista.Position<E> root()
                                    throws EmptyTreeException

      Description copied from interface: `GTTree`
      Devuelve la posición de la raíz del árbol.
      Specified by:
        `root` in interface `GTTree<E>`
      Returns:
        Posición de la raíz del árbol.
      Throws:
        `EmptyTreeException` - si el árbol está vacío.

    - #### parent

          public TDALista.Position<E> parent(TDALista.Position<E> v)
                                      throws TDALista.InvalidPositionException,
                                             TDALista.BoundaryViolationException

      Description copied from interface: `GTTree`
      Devuelve la posición del nodo padre del nodo correspondiente a una posición dada.
      Specified by:
        `parent` in interface `GTTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Posición del nodo padre del nodo correspondiente a la posición dada.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.
        `TDALista.BoundaryViolationException` - si la posición pasada por parámetro corresponde a la raíz del árbol.

    - #### children

          public java.lang.Iterable<TDALista.Position<E>> children(TDALista.Position<E> v)
                                                            throws TDALista.InvalidPositionException

      Description copied from interface: `GTTree`
      Devuelve una colección iterable de los hijos del nodo correspondiente a una posición dada.
      Specified by:
        `children` in interface `GTTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Colección iterable de los hijos del nodo correspondiente a la posición pasada por parámetro.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.

    - #### isInternal

          public boolean isInternal(TDALista.Position<E> v)
                             throws TDALista.InvalidPositionException

      Description copied from interface: `GTTree`
      Consulta si una posición corresponde a un nodo interno.
      Specified by:
        `isInternal` in interface `GTTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Verdadero si la posición pasada por parámetro corresponde a un nodo interno, falso en caso contrario.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.

    - #### isExternal

          public boolean isExternal(TDALista.Position<E> v)
                             throws TDALista.InvalidPositionException

      Description copied from interface: `GTTree`
      Consulta si una posición dada corresponde a un nodo externo.
      Specified by:
        `isExternal` in interface `GTTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Verdadero si la posición pasada por parámetro corresponde a un nodo externo, falso en caso contrario.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.

    - #### isRoot

          public boolean isRoot(TDALista.Position<E> v)
                         throws TDALista.InvalidPositionException

      Description copied from interface: `GTTree`
      Consulta si una posición dada corresponde a la raíz del árbol.
      Specified by:
        `isRoot` in interface `GTTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Verdadero, si la posición pasada por parámetro corresponde a la raíz del árbol,falso en caso contrario.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.

    - #### left

          public TDALista.Position<E> left(TDALista.Position<E> v)
                                    throws TDALista.InvalidPositionException,
                                           TDALista.BoundaryViolationException

      Description copied from interface: `BinaryTree`
      Devuelve la posición del hijo izquierdo de v.
      Specified by:
        `left` in interface `BinaryTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Posición del hijo izquierdo de v.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.
        `TDALista.BoundaryViolationException` - si v no tiene hijo izquierdo.

    - #### right

          public TDALista.Position<E> right(TDALista.Position<E> v)
                                     throws TDALista.InvalidPositionException,
                                            TDALista.BoundaryViolationException

      Description copied from interface: `BinaryTree`
      Devuelve la posición del hijo derecho de v.
      Specified by:
        `right` in interface `BinaryTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Posición del hijo derecho de v.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.
        `TDALista.BoundaryViolationException` - si v no tiene hijo derecho.

    - #### hasLeft

          public boolean hasLeft(TDALista.Position<E> v)
                          throws TDALista.InvalidPositionException

      Description copied from interface: `BinaryTree`
      Testea si v tiene un hijo izquierdo.
      Specified by:
        `hasLeft` in interface `BinaryTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Verdadero si v tiene un hijo izquierdo y falso en caso contrario.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.

    - #### hasRight

          public boolean hasRight(TDALista.Position<E> v)
                           throws TDALista.InvalidPositionException

      Description copied from interface: `BinaryTree`
      Testea si v tiene un hijo derecho.
      Specified by:
        `hasRight` in interface `BinaryTree<E>`
      Parameters:
        `v` - Posición de un nodo.
      Returns:
        Verdadero si v tiene un hijo derecho y falso en caso contrario.
      Throws:
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida.

    - #### createRoot

          public TDALista.Position<E> createRoot(E r)
                                          throws InvalidOperationException

      Description copied from interface: `BinaryTree`
      Crea un nodo con rótulo e como raíz del árbol.
      Specified by:
        `createRoot` in interface `BinaryTree<E>`
      Throws:
        `InvalidOperationException` - si el árbol ya tiene un nodo raíz.

    - #### addLeft

          public TDALista.Position<E> addLeft(TDALista.Position<E> v,
                                              E r)
                                       throws InvalidOperationException,
                                              TDALista.InvalidPositionException

      Description copied from interface: `BinaryTree`
      Agrega un nodo con rótulo r como hijo izquierdo de un nodo dado.
      Specified by:
        `addLeft` in interface `BinaryTree<E>`
      Parameters:
        `v` - Posición del nodo padre.
        `r` - Rótulo del nuevo nodo.
      Returns:
        La posición del nuevo nodo creado.
      Throws:
        `InvalidOperationException` - si v ya tiene un hijo izquierdo.
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida o el árbol está vacío.

    - #### addRight

          public TDALista.Position<E> addRight(TDALista.Position<E> v,
                                               E r)
                                        throws InvalidOperationException,
                                               TDALista.InvalidPositionException

      Description copied from interface: `BinaryTree`
      Agrega un nodo con rótulo r como hijo derecho de un nodo dado.
      Specified by:
        `addRight` in interface `BinaryTree<E>`
      Parameters:
        `v` - Posición del nodo padre.
        `r` - Rótulo del nuevo nodo.
      Returns:
        La posición del nuevo nodo creado.
      Throws:
        `InvalidOperationException` - si v ya tiene un hijo derecho.
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida o el árbol está vacío.

    - #### remove

          public E remove(TDALista.Position<E> v)
                   throws InvalidOperationException,
                          TDALista.InvalidPositionException

      Description copied from interface: `BinaryTree`
      Elimina el nodo referenciado por una posición dada. Si el nodo tiene un único hijo, el nodo eliminado será reemplazado por su único hijo.
      Specified by:
        `remove` in interface `BinaryTree<E>`
      Parameters:
        `v` - Posición del nodo a eliminar.
      Returns:
        el rótulo del nodo eliminado.
      Throws:
        `InvalidOperationException` - si el nodo a eliminar tiene mas de un hijo.
        `TDALista.InvalidPositionException` - si la posición pasada por parámetro es inválida o el árbol está vacío.